//1.sort
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if(n==0) return;
        for(int i=0;i<n;++i)
            nums1[m+i]=nums2[i];
        sort(nums1.begin(), nums1.end());
        return ;
    }
};
//2. 合并有序链表的思路--空间复杂度有点大
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if(n==0) return;
        int temp[m+n];
        int i=0,j=0;
        int cur;
        while(i<m || j <n) {
            if(i==m) cur = nums2[j++];
            else if(j==n) cur = nums1[i++];
            else if(nums1[i] <= nums2[j])  cur = nums1[i++];
            else cur = nums2[j++];

            temp[i+j-1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = temp[i];
        }
        return ;
    }
};
//3.优化空间---从后往前合并
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;         // nums1 的有效末尾
        int j = n - 1;         // nums2 的末尾
        int k = m + n - 1;     // nums1 的总末尾（写入位置）
        while(i>=0 && j>=0) {
            if(nums1[i] <= nums2[j]) {
                nums1[k] = nums2[j];
                k--;j--;
            } else {
                nums1[k] = nums1[i];
                k--;i--;
            }
        }
        while(j>=0) {
            nums1[k] = nums2[j];
            k--;j--;
        }
       return;
    }
};



